#include <cstring>
#include "common.h"

using namespace std;

// 回溯算法
namespace {

bool isContain(int num, VectorInt &track) {
    for (auto iter = track.begin(); iter !=  track.end(); iter++) {
        if (*iter == num) {
            return true;
        }
    }
    return false;
}

bool backtrack(VectorInt &nums,  VectorInt &track) {
    // 找到结果
    if (track.size() == nums.size()) {
        std::cout << track << std::endl;
        return true;
    }

    for (int i=0; i<nums.size(); i++) {
        // 已经选择过
        if (isContain(nums[i], track)) continue;

        // 符合条件
        track.push_back(nums[i]);
    
        // 递归
        if (backtrack(nums, track))
            return true;

        // 回溯
        track.pop_back();
    }

    return false;
}

void permute(VectorInt &nums) {
    VectorInt track;
    backtrack(nums, track);
}

bool isValid(vector<string> &board, int row, int col) {
    int n = board.size();

    // 检查列
    for (int i=0; i<n; i++) {
        if (board[i][col] == 'Q')
            return false;
    }

    // 右上方
    for (int i=row-1, j=col+1; i>=0 && j<n; i--, j++) {
        if (board[i][j] == 'Q')
            return false;
    }

    // 左上方
    for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
        if (board[i][j] == 'Q')
            return false;
    }

    return true;
}

void backtrack2(vector<string> &board, int row) {
    if (row == board.size()) {
        std::cout << board << std::endl;
        return;
    }

    int n = board[row].size();
    for (int col=0; col<n; col++) {
        if (!isValid(board, row, col)) continue;

        board[row][col] = 'Q';

        backtrack2(board, row + 1);

        board[row][col] = '.';
    }
}

// N皇后问题
void solveNQueens(int n) {
    vector<string> board(n, string(n, '.'));
    backtrack2(board, 0);
}

bool isValidSudoku(int board[9][9]) {
    const int size = 9;
    bool rows[size][size] = {false};
    bool cols[size][size] = {false};
    bool cubes[size][size] = {false};
    for (int i=0; i<size; ++i) {
        for (int j=0; j<size; ++j) {
            if (board[i][j] == 0) continue;
            int num = board[i][j] - 0 - 1;
            int k = i / 3 * 3 + j / 3;
            if (rows[i][num] || cols[j][num] || cubes[k][num])
                return false;
            rows[i][num] = cols[j][num] = cubes[k][num] = true;
        }
    }
    return true;
}

bool isOk(int board[9][9], int row, int col, int value) {
    // 检查行
    for (int i=0; i<9; i++) {
        if (board[i][col] == value)
            return false;
    }

    // 检查列
    for (int i=0; i<9; i++) {
        if (board[row][i] == value)
            return false;
    }

    // 检查grid
    int m = row / 3 * 3;
    int n = col / 3 * 3;
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            if (board[i+m][j+n] == value)
                return false;
        }
    }

    // // 非标准数独，对角线不重复
    // if (row == col) {
    //     for (int i=0; i<9; i++) {
    //         if (board[i][i] == value)
    //             return false;
    //     }
    // }
    // if (row + col == 8) {
    //     for (int i=0; i<9; i++) {
    //         if (board[i][8-i] == value)
    //             return false;
    //     }
    // }

    return true;
}

bool backtrack3(int board[9][9], int row, int col) {
    // 到达最后一行最后一列
    if (row == 8 && col == 9) {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                std::cout << board[i][j] << ",";
            }
            std::cout << std::endl;
        }
        return true;
    }

    // 换行
    if (col == 9) {
        col = 0;
        row++;
    }

    if (board[row][col] != 0)
        return backtrack3(board, row, col + 1);

    for (int num=1; num<=9; num++) {
        if (!isOk(board, row, col, num)) continue;

        board[row][col] = num;

        if (backtrack3(board, row, col + 1))
            return true;
    }

    board[row][col] = 0;
    return false;
}

void solveSudoku(int board[9][9]) {
    backtrack3(board, 0, 0);
}

vector<VectorInt> resSets;
void backtrack4(const VectorInt &nums, int start, VectorInt &track) {
    resSets.push_back(track);
    for (int i=start; i<nums.size(); i++) {
        track.push_back(nums[i]);
        backtrack4(nums, i + 1, track);
        track.pop_back();
    }
}

// 求子集问题
vector<VectorInt> subsets(const VectorInt &nums) {
    VectorInt track;
    backtrack4(nums, 0, track);
    vector<VectorInt> &sets = resSets;
    for (int i=0; i<sets.size(); i++) {
        std::cout << sets[i] << std::endl;
    }
    return resSets;
}

// 1、左右括号肯定成对出现
// 2、循环过程中，左括号数量肯定大于右括号数量
void backtrack5(int left, int right, string &track, vector<string> &res) {
    if (right < left) return;

    // 左右数量不匹配
    if (left < 0 || right < 0) return;

    // 找到一组
    if (left == 0 && right == 0) {
        res.push_back(track);
        return;
    }

    // 放个左括号
    track.push_back('(');
    backtrack5(left - 1, right, track, res);
    track.pop_back();

    // 放个右括号
    track.push_back(')');
    backtrack5(left, right - 1, track, res);
    track.pop_back();
}

// 括号组合
// 输入n，输出n多可能的括号组合
vector<string> generateParenthesis(int n) {
    string track;
    vector<string> res;
    backtrack5(n, n, track, res);
    std::cout << res << std::endl;
    return res;
}

void Handle() {
    VectorInt nums = {1,2,3};
    permute(nums);

    solveNQueens(4);

    int sudoku[9][9] = {
        {9,0,0,0,0,0,0,0,1},
        {0,0,0,0,4,0,0,0,0},
        {8,0,0,1,0,0,0,9,0},
        {0,0,0,0,5,0,0,0,0},
        {0,0,0,0,0,6,0,0,0},
        {0,7,0,0,0,0,3,0,8},
        {0,0,0,9,0,0,0,0,0},
        {0,2,0,0,0,0,0,1,7},
        {6,0,0,0,0,2,0,8,9}
    };
    std::cout << "is valid sudoku1 " << isValidSudoku(sudoku) << std::endl;
    solveSudoku(sudoku);
    std::cout << "is valid sudoku2 " << isValidSudoku(sudoku) << std::endl;

    subsets({1,2,3});

    generateParenthesis(4);
}
}

void HandleBacktrack() {
    Handle();
}